#include <iostream>
#include <vector>

using namespace std;
// 35. 搜索插入位置
// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
class Solution {
private:
    int lowerbound(vector<int>& nums, int n, int k) {
        int low = 0, high = n;
        while(low < high) {
            int mid = low + (high-low) / 2;
            if(k <= nums[mid]) {
                high = mid;
            } else {
                low = mid+1;
            }
        }
        return low;
    }
public:
    int searchInsert(vector<int>& nums, int target) {
        return lowerbound(nums,nums.size(),target);
    }
};
int main() {
    vector<int> nums1 = {1,3,5,6};
    std::cout << Solution().searchInsert(nums1,5) << std::endl; // 2
    std::cout << Solution().searchInsert(nums1,2) << std::endl; // 1
    std::cout << Solution().searchInsert(nums1,7) << std::endl; // 4
    return 0;
}
